package cn.bouncyslime.algorithms.stack.parenthesesMatching;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 括号匹配检验，判断开放符号是否有对应的封闭符号，并且符号的顺序是否是正确的
 * 作者：张一卓
 * 创建日期：2020/10/9
 */
public class ParenthesesMatching {
    public static void main(String[] args) {
        String[] parenthesesArray = {"{[]([][])}", "{[(])[(()[])]}", "}}[]"};
        for (String parentheses : parenthesesArray){
            parenthesesMatching(parentheses);
        }
    }

    public static void parenthesesMatching(String parentheses){
        System.out.println(">>> 括号序列为 " + parentheses);
        Deque<Character> stack = new LinkedList<>();
        for (int i=0; i<parentheses.length(); i++){
            char parenthese = parentheses.toCharArray()[i];
            stack.push(parenthese);
            if (parenthese == ')' || parenthese == ']' || parenthese == '}'){
                stack.pop();
                if (stack.isEmpty()){
                    System.out.println("括号不匹配，闭括号 " + parenthese + " 开头");
                    return;
                }
                Character stackTopChar = stack.pop();
                if ((stackTopChar == '(' && parenthese != ')') ||
                        (stackTopChar == '[' && parenthese != ']') ||
                        (stackTopChar == '{' && parenthese != '}')){
                    System.out.println("括号不匹配，不匹配括号对" + stackTopChar + "" + parenthese + "，不匹配位置（起始0）= " + i);
                    return;
                }
            }
        }
        System.out.println("括号序列顺序正确");
    }
}
